1. Technical Field
The invention relates in general to an apparatus and a method for split-radix-2/8 Fast Fourier Transform.
2. Background
Fast Fourier Transform (FFT) is often used in real-time applications for the digital signal processing. An orthogonal frequency division multiplexer (OFDM) system is widely used in European Digital Video Broadcasting terrestrial (DVB-T)/Digital Audio Broadcasting (DAB) standard, and a dedicated FFT/IFFT processing unit is further suitable for the OFDM system and the digital communication to obtain wide frequency range.
It is well known that in the FFT algorithm, the split-radix-2/8 (SR-2/8) FFT algorithm can save about ⅓ complex multiplication compared with the radix-4 FFT. The SR-2/8 FFT is shown as the following even FFT terms and odd FFT terms. Referring concurrently now to FIGS. 6 and 7, FIG. 6 shows a schematic illustration illustrating a decimation in frequency (DIF) SR-8 butterfly computation, and FIG. 7 shows a schematic illustration illustrating a decimation in time (DIT) SR-8 butterfly computation.
            X      ⁡              (                  2          ⁢          k                )              =                  ∑                  n          =          0                                      N            /            2                    -          1                    ⁢                        (                                    x              ⁡                              (                n                )                                      +                          x              ⁡                              (                                  n                  +                                      N                    2                                                  )                                              )                ⁢                  W                      N            /            2                    nk                                where      ⁢                          ⁢              W                  N          /          2                      =                  ⅇ                              -            j                    ⁢                                          ⁢                                    2              ⁢              π                                      N              /              2                                          ⁢                          ⁢      and                  k      =      0        ,    1    ,    2    ,    …    ⁢                  ,                  (                  N          /          2                )            -              1        ⁢                  (                      even            ⁢                                                  ⁢            FFT            ⁢                                                  ⁢            term                    )                      And            X      ⁡              (                              8            ⁢            k                    +          l                )              =                  ∑                  n          =          0                                      N            /            8                    -          1                    ⁢                        (                                                                                          (                                                                  x                        ⁡                                                  (                          n                          )                                                                    +                                                                        x                          ⁡                                                      (                                                          n                              +                                                                                                2                                  ⁢                                  N                                                                8                                                                                      )                                                                          ⁢                                                  W                          4                          l                                                                    +                                                                        x                          ⁡                                                      (                                                          n                              +                                                                                                4                                  ⁢                                  N                                                                8                                                                                      )                                                                          ⁢                                                  W                          4                                                      2                            ⁢                            l                                                                                              +                                                                        x                          ⁡                                                      (                                                          n                              +                                                                                                6                                  ⁢                                  N                                                                8                                                                                      )                                                                          ⁢                                                  W                          4                                                      -                            l                                                                                                                )                                    +                                                                                                                          (                                                                                                                                                      x                              ⁡                                                              (                                                                  n                                  +                                                                      N                                    8                                                                                                  )                                                                                      +                                                                                          x                                ⁡                                                                  (                                                                      n                                    +                                                                                                                  3                                        ⁢                                        N                                                                            8                                                                                                        )                                                                                            ⁢                                                              W                                4                                l                                                                                      +                                                                                                                                                                                                          x                              ⁢                                                              (                                                                  n                                  +                                                                                                            5                                      ⁢                                      N                                                                        8                                                                                                  )                                                            ⁢                                                              W                                4                                                                  2                                  ⁢                                  l                                                                                                                      +                                                                                          x                                ⁡                                                                  (                                                                      n                                    +                                                                                                                  7                                        ⁢                                        N                                                                            8                                                                                                        )                                                                                            ⁢                                                              W                                4                                                                  -                                  l                                                                                                                                                                                                          )                                    ⁢                                      W                    8                                          -                      l                                                                                                    )                ⁢                  W          N          nl                ⁢                  W                      N            /            8                    nk                                        where        ⁢                                  ⁢        k            =      0        ,    1    ,    2    ,    …    ⁢                  ,                            (                      N            /            8                    )                -                  1          ⁢                                          ⁢          and          ⁢                                          ⁢          l                    =      1        ,    3    ,    5    ,    7    ⁢          (              odd        ⁢                                  ⁢        FFT        ⁢                                  ⁢        term            )      Thus, the SR-2/8 algorithm can make use of resources or time more efficiently. However, the irregular decomposition structure of the SR-2/8 FFT algorithm causes that the SR-2/8 FFT is hard to be implemented in hardware, and the SR-2/8 FFT is generally regarded as more suitably to be implemented in software.
Take the SR-2/4 FFT algorithm as being exemplified. Butterfly processors of the SR-2/4 FFT and the radix-4 FFT both have 4 inputs and 4 outputs. Corresponding to a fixed input clock and limited hardware resources, data accessing between the memory and the butterfly processor has to be as fast as possible. The maximum speed of the FFT can be obtained by simultaneously reading and writing the 4 inputs of the butterfly processor of the SR-2/4 FFT; thus each butterfly computation only consumes only one clock cycle.
Assume that the memory includes 4 memory banks. An input data sequence of a DIT radix-4 butterfly as the butterfly processor of the radix-4 FFT processes 16 pieces of input data is shown in Table 1.
TABLE 1Stage 1Stage 2(0, 8, 4, 12)(0, 2, 1, 3)(1, 9, 5, 13)(8, 10, 9, 11)(2, 10, 6, 14)(4, 6, 5, 7)(3, 11, 7, 15)(12, 14, 13, 15)
In Table 1, before stage 1 starts, data 0 to data 3 are located in the memory bank 0, data 8 to data 11 are located in the memory bank 1, data 4 to data 7 are located in the memory bank 2, and data 12 to data 15 are located in the memory bank 3. Therefore, the 4 inputs of the radix-4 butterfly processor can simultaneously read data, such as (0, 8, 4, 12), in a single clock cycle at stage 1. However, at stage 2, the radix-4 butterfly processor needs to take 4 clock cycles to read data, such as (0, 2, 1, 3) from the memory. Consequently, the speed of the entire FFT operation slows down, thus lowering the overall system performance.